package com.cg.leetcode;

import org.junit.Test;

import java.util.*;

/**
 * 155. 最小栈
 *
 * @program: LeetCode->LeetCode_155
 * @description: 155. 最小栈
 * @author: cg
 * @create: 2021-08-27 17:14
 **/
public class LeetCode_155 {

    @Test
    public void test155() {
        MinStack minStack = new MinStack();
        minStack.push(2);
        minStack.push(0);
        minStack.push(3);
        minStack.push(0);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        //System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }

    /**
     * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
     * <p>
     * push(x) —— 将元素 x 推入栈中。
     * pop() —— 删除栈顶的元素。
     * top() —— 获取栈顶元素。
     * getMin() —— 检索栈中的最小元素。
     * <p>
     * 示例:
     * <p>
     * 输入：
     * ["MinStack","push","push","push","getMin","pop","top","getMin"]
     * [[],[-2],[0],[-3],[],[],[],[]]
     * <p>
     * 输出：
     * [null,null,null,null,-3,null,0,-2]
     * <p>
     * 解释：
     * MinStack minStack = new MinStack();
     * minStack.push(-2);
     * minStack.push(0);
     * minStack.push(-3);
     * minStack.getMin();   --> 返回 -3.
     * minStack.pop();
     * minStack.top();      --> 返回 0.
     * minStack.getMin();   --> 返回 -2.
     * <p>
     * 提示：
     * pop、top 和 getMin 操作总是在 非空栈 上调用。
     */
    class MinStack {

        Deque<Integer> stack;
        Deque<Integer> minStack;

        public MinStack() {
            stack = new LinkedList<Integer>();
            minStack = new LinkedList<Integer>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int val) {
            stack.push(val);
            minStack.push(Math.min(minStack.peek(), val));
        }

        public void pop() {
            stack.pop();
            minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }
/*    class MinStack {
        //自己实现栈
        private static final int MIN_SIZE = 5;
        private int[] stack;
        private int index;

        public MinStack() {
            stack = new int[MIN_SIZE];
            index = -1;
        }

        public void push(int val) {
            if (index + 1 >= MIN_SIZE) {
                int[] clone = stack.clone();
                stack = new int[clone.length + MIN_SIZE];
                System.arraycopy(clone, 0, stack, 0, clone.length);
            }
            stack[++index] = val;
        }

        public void pop() {
            stack[index--] = Integer.MAX_VALUE;
        }

        public int top() {
            return stack[index];
        }

        public int getMin() {
            int min = stack[0];
            for (int i = 1; i <= index; i++) {
                if (stack[i] < min) {
                    min = stack[i];
                }
            }
            return min;
        }
    }*/

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

}
